package sort;

import java.util.Arrays;

/**
 * @author RunningShrimp
 * @date 2021/6/16  14:32
 * @see <a href=""></a>
 */
public class BucketSort extends BaseSort<Integer> {
    @Override
    public void sort(Integer[] array) {
        int bucketSize = 5;
        Integer maxValue = array[0];
        Integer minValue = array[0];
        for (Integer e : array) {
            if (less(maxValue, e)) {
                maxValue = e;
            } else if (less(e, minValue)) {
                minValue = e;
            }
        }

        int bucketCount = (int) Math.floor((maxValue - minValue) / bucketSize) + 1;
        Integer[][] buckets = new Integer[bucketCount][0];

        for (Integer integer : array) {
            int index = (int) Math.floor((integer - minValue) / bucketSize);
            buckets[index] = arrAppend(buckets[index], integer);
        }
        int arrIndex = 0;
        for (Integer[] bucket : buckets) {
            if (bucket.length <= 0) {
                continue;
            }
            // 对每个桶进行排序，这里使用了插入排序
            new InsertionSort<Integer>().sort(bucket);
            for (Integer value : bucket) {
                array[arrIndex++] = value;
            }
        }
    }

    /**
     * 自动扩容，并保存数据
     *
     * @param arr
     * @param value
     */
    private Integer[] arrAppend(Integer[] arr, Integer value) {
        arr = Arrays.copyOf(arr, arr.length + 1);
        arr[arr.length - 1] = value;
        return arr;
    }

    public static void main(String[] args) {
        Integer[] array = BaseSort.generateArray(5, 100);
        BaseSort<Integer> sort = new BubbleSort<>();

        System.out.println("排序前：");
        sort.show(array);
        sort.sort(array);
        System.out.println("排序后");
        sort.show(array);
        System.out.println("是否有序：" + sort.isSorted(array));
    }
}
